package com.ywgt;

import java.util.Arrays;

/**
 * 归并排序
 */
public class Merge {
    public static void main(String[] args) {
        int [] arr={125,26,266,15,0,124};
        int [] temp=new int[arr.length];
        sort(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int [] arr,int left,int right,int []temp){
        if(left<right){//满足条件时拆分
            int mid=(left+right)/2;
            sort(arr,left,mid,temp);
            sort(arr,mid+1,right,temp);
            merge(arr,left,mid,right,temp); //进行合并 从上面的栈压完后，从栈顶开始合并
        }
    }

    public static void merge(int [] arr,int left,int mid,int right,int [] temp){
        int i=left; //左侧下标
        int j=mid+1; //右侧下标
        int t=0; //临时数组下标
        //当两个数组中的有一个为空时退出循环
        while(i<=mid&&j<=right){
            if(arr[i]<=arr[j]){
               temp[t]=arr[i];
                t+=1;
                i+=1;
            }else {
                temp[t]=arr[j];
                t+=1;
                j+=1;
            }
        }
        //合并
        while(i<=mid){
            temp[t]=arr[i];
            t+=1;
            i+=1;
        }
        while(j<=right){
            temp[t]=arr[j];
            t+=1;
            j+=1;
        }
        //将temp里面的数组拷贝到arr数组中
        t=0;
        int leftTemp=left; //每次都是将全部的tem中的元素拷贝到arr中，但是起始位置从每次left位置开始 拷贝传进来的数组大小个
        while(leftTemp<=right){
            arr[leftTemp]=temp[t];
            t+=1;
            leftTemp+=1;
        }
    }
}
